import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] arr = new int[]{};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr) {
        /**
         * 快速排序
         *  递归实现的二路快排（三路快排可以对重复值做到较好的处理，二路快排不能）*/
        dfs(arr, 0, arr.length-1);
    }

    public static void dfs(int[] arr, int left, int right) {
        /**
         * 快速排序递归部分
         * @parameter left: 左边界
         * @parameter right: 右边界
         * 上述均是闭区间*/
        // 1 递归出口
        if(left >= right) {
            return;
        }

        // 2 找基准值
        int pivot = partition(arr, left, right);

        // 3 左右区间递归
        dfs(arr, left, pivot-1);
        dfs(arr, pivot+1, right);
    }

    public static int partition(int[] arr, int left, int right) {
        /**
         * 将数组按照基准值划分为两部分，左边为小于等于基准值，右边为大于基准值，返回基准值下标*/
        // 1 预处理
        int baseIndex = left;
        int base = arr[left];

        // 2 按照基准值划分
        while(left < right) {
            // -遍历右边，遇见第一个小于基准值的元素时停止
            while(left < right && arr[right] >= base) {
                right --;
            }
            // -遍历左边，遇见第一个大于基准值的元素时停止
            while(left < right && arr[left] <= base) {
                left ++;
            }
            // -交换左右
            swap(arr, left, right);
        }

        // 3 出循环时，left和right均指向基准值，将基准值交换至分割点
        swap(arr, baseIndex, left);
        return left;
    }

    public static void bubbleSort(int[] arr) {
        /**
         * 冒泡排序
         *  每轮使待排序区间中的最大值有序
         *  n个元素排序n-1轮*/
        // 1 预处理
        int n = arr.length;

        // 2 排序逻辑
        for(int i = 0; i < n-1; i++) { // -外层循环枚举轮次
            boolean flag = true;
            for(int j = 0; j < n-1-i; j++) { // -内层循环遍历待排序区间
                if(arr[j] > arr[j+1]) {
                    swap(arr, j, j+1);
                    flag = false;
                }
            }
            // -若是一轮中没有交换产生，说明已经有序，直接返回
            if(flag) {
                break;
            }
        }
    }

    public static void swap(int[] arr, int i, int j) {
        /**
         * 交换数组中两个元素的小标*/
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
